The present invention relates to forwarding for network devices. More specifically, the invention relates to optimizing forwarding that can be utilized on provider edge routers that use the EBGP protocol.
A router is a hardware device that stores and forwards data packets from one hardware device to another. The different hardware devices can be on the same local area network (LAN) or within the same wide area network (WAN). One such wide area network is the Internet.
Support for full Internet routing places a heavy burden on a router. In some cases, the hardware capability of a router which is at the edge of a service provider's network may be constrained to be low due to space, power and other constraints. In such a situation, it becomes especially hard to support full Internet routing at wire rates without having to resort to static routing or some default routing technique.
One of the difficulties in implementing full Internet routing is the size of the routing table. In general, the routing table needs to accommodate every Internet route that the service provider's router becomes aware. For example, it is possible that the routing table may need to store hundreds of thousands of routes. The sheer size of the routing table may require higher processing power for accessing the table and larger storage requirements. In addition with a large routing table the processor in the router has to spend a great percentage of time managing and maintaining the entries in the table thereby not being able to service other tasks on the router in a timely manner. Hence a more powerful processor is need in order to do both efficiently. As the size of the Internet continues to grow rapidly, the severity of these problems continues to increase.
Conventional techniques for addressing this problem have been inadequate. As an example, techniques can be utilized to improve the searching efficiency of a large routing table. Also, internet protocol (IP) address prefix patterns can be identified in order to use address aggregation to reduce the size of the routing table (e.g., CIDR based route aggregation).
Accordingly, it would be beneficial to have innovative techniques for implementing forwarding for network devices. Additionally, it would be beneficial if improvements in a service provider's edge router can be achieved without requiring modification to other routers to which it communicates.